#pragma once
//存放所有库头文件
#include<iostream>
#include<vector>
#include<time.h>
#include<assert.h>
#include<thread>
#include<mutex>
#include<unordered_map>
#include<map>
//#include <algorithm>
//#include<memoryapi.h>

#ifdef _WIN32
	#include<windows.h>
#endif

using std::cout;
using std::endl;

//通过条件编译处理32/64位系统下的page大小
#ifdef  _WIN64              //64位下_WIN64和_WIN32都有
	typedef unsigned long long PAGE_ID;    //8字节
#elif _WIN32				//32位下仅有_WIN32
	typedef size_t PAGE_ID;   //4字节
#endif // !

//静态全局变量，代替宏定义
static const size_t MAX_BYTES=256 * 1024;    //256KB
static const size_t NFREELISTS = 208;         //总哈希桶个数
static const size_t NPAGE = 129;             //PageCache 桶的总个数
static const size_t PAGE_SHIFT = 13;          //定义一页为8K（1024*8）

//直接在堆上申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif
	//64位，linux
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
//堆上释放
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap
#endif
}

static void*& NextObj(void* obj)
{
	//指向该对象的地址：即为该对象的地址空间
	return *(void**)obj;   //*(void**)  用于处理32、64位系统下指针长度的不同
}

//管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)    //头插      freelist为链表头头
	{
		assert(obj);
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;     //obj的前4/8为存储freelist指向的对象
		_freeList = obj;              //freelist再指向obj，完成头插
		_size+=1;
	}

	void PushRange(void* start, void* end,size_t n)    //范围性头插
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}

	void PopRange(void*& start, void*& end, size_t n)    //范围性头删n个
	{
		assert(n <= _size);
		start = _freeList;
		//end = start;
		for (int i = 0; i < n; i++)
		{
			end = _freeList;
			_freeList = NextObj(_freeList);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
 		_size -= n;
	}

	void* Pop()   //头删
	{
		void* obj = _freeList;       //obj存储freelist指向的对象的地址
		assert(obj);
		_freeList = NextObj(obj);      //完成头删
		_size -= 1;
		return obj;
	}
	bool Empty()    //判空
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
 		return maxSize;
	}
	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList=nullptr;
	size_t maxSize = 1;
	size_t _size=0;
};


//计算对象大小的对齐，管理对齐映射规则
class SizeClass
{
//最开始按8字节对齐，保证32/64位系统下都可以存放下指针
public:
	// 整体控制在最多10%左右的内碎片浪费            弄清楚计算方法
   // [1,128]                   8byte对齐（每个桶的单位内存大小）    freelist[0,16)（该区间的桶数）
   // [128+1,1024]              16byte对齐                           freelist[16,72)
   // [1024+1,8*1024]           128byte对齐							 freelist[72,128)
   // [8*1024+1,64*1024]        1024byte对齐						 freelist[128,184)
   // [64*1024+1,256*1024]      8*1024byte对齐						 freelist[184,208)
	
   //高阶方法
   /*static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		return ((size + alignNum - 1) & ~(alignNum - 1));
	}*/

	//计算经过对齐处理后所申请的空间（上面是高阶策略）
	static inline size_t _RoundUp(size_t size, size_t alignNum)   //alignNum：对齐数
	{
		size_t alignSize;            //对齐后的内存大小
		if (size % alignNum != 0)       //==0 则不用再额外补充空间
		{
			alignSize = (size / alignNum + 1) * alignNum;
		}
		else
		{
			alignSize = size;
		}
		return alignSize;
	}

	static inline size_t RoundUp(size_t size)     //选择分配单位内存大小
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8*1024);
		}
		else
		{
			//assert(false);      //该规则最大允许256KB，超过则不允许采用该过程
			//return -1;
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	//计算对应内存碎片在自身区间的下标
	static inline size_t _Index(size_t size,size_t align_shit)   //align_shit:align调整为二进制位数
	{   //弄清规则原理
		return ((size + (1 << align_shit) - 1) >> align_shit )- 1;
	}

	//常规方法计算下标，下面是高阶方法
	//static inline size_t _Index0(size_t size, size_t alignum)
	//{
	//	if (alignum == 8)
	//	{
	//		return size / alignum;
	//	}
	//	else if (alignum == 16)
	//	{
	//		return (size - 128) / alignum + 128 / 8;
	//	}
	//	//TODO.......
	//}

	static inline size_t Index(size_t size)
	{
		//assert(size <= MAX_BYTES);

		//每个区间的桶数
		static int group_array[4] = { 16,56,56,56 };
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size-128, 4)+group_array[0];       //补上上一区间的总桶数
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size - 8*1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size - 64*1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else
		{
			assert(false);
		}
		return -1;
	}

	//Centralcache向threadcache转移的内存块数
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		//调整转移数量，避免给的太多
		int num = MAX_BYTES / size;   
		if (num < 2)
			num=2;
		if (num > 512)
			num=512;

		return num;
	}

	//计算一次向系统要多少页
	//单个对象8	byte
	//.....
	//单个对象256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;        //右移

		if (npage == 0)
			npage = 1;
		return npage;
	}
};

//管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageid=0;      //大块内存起始页页号
	size_t _n=0;			//页的数量

	Span* _next=nullptr;    //双向链表结构
	Span* _prev = nullptr;

	size_t objectSize = 0;       //切好的内存块大小
	size_t _useCount=0;		//切好的小内存块，被分配给thread_cache的数量（_useCount==0,则可得知被全部归还）
	void* _freeList=nullptr;		//切好的内存块的自由链表

	bool _isUse=false;                   //判断span是否在被使用
};

//带头的双向链表结构   CentralCache区域
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* begin()         //双向链表的头
	{
		return _head->_next;
	}

	Span* end()          //双向链表的尾
	{
		return _head;
	}

	bool Empty()     //判空
	{
		return _head->_next == _head;
	}

	void PushFront(Span* span)        //头插
	{
		Insert(begin(), span);
	}

	Span* PopFront()       //头删
	{
		Span* front = _head->_next;
		Erase(front);               //解下head后的span
		return front;
	}

	void Insert(Span* pos,Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;    //双向链表插入
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
		//newSpan->_next = pos;
	}

	void Erase(Span* pos)     //未进行delete
	{
		assert(pos);
		assert(pos != _head);       //不能删头结点
		//条件断点    查看栈帧进行调试
		if (pos == _head)
		{

		}

		Span* prev = pos->_prev;    //双链表头删
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
private:
	Span* _head;    //头结点
public:
	std::mutex _mtx;    //桶锁，只用来对不同的桶加锁，而不是整个Central_cache区域，避免不同桶之间阻塞
};